package com.sheng.leetcode.year2024.month04.day26;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * @author by ls
 * @date 2024/4/26
 * <p>
 * 1146. 快照数组<p>
 * <p>
 * 实现支持下列接口的「快照数组」- SnapshotArray：<p>
 * SnapshotArray(int length) - 初始化一个与指定长度相等的 类数组 的数据结构。初始时，每个元素都等于 0。<p>
 * void set(index, val) - 会将指定索引 index 处的元素设置为 val。<p>
 * int snap() - 获取该数组的快照，并返回快照的编号 snap_id（快照号是调用 snap() 的总次数减去 1）。<p>
 * int get(index, snap_id) - 根据指定的 snap_id 选择快照，并返回该快照指定索引 index 的值。<p>
 * <p>
 * 示例：<p>
 * 输入：["SnapshotArray","set","snap","set","get"]<p>
 * [[3],[0,5],[],[0,6],[0,0]]<p>
 * 输出：[null,null,0,null,5]<p>
 * 解释：<p>
 * SnapshotArray snapshotArr = new SnapshotArray(3); // 初始化一个长度为 3 的快照数组<p>
 * snapshotArr.set(0,5);  // 令 array[0] = 5<p>
 * snapshotArr.snap();  // 获取快照，返回 snap_id = 0<p>
 * snapshotArr.set(0,6);<p>
 * snapshotArr.get(0,0);  // 获取 snap_id = 0 的快照中 array[0] 的值，返回 5<p>
 * <p>
 * 提示：<p>
 * 1 <= length <= 50000<p>
 * 题目最多进行50000 次set，snap，和 get的调用 。<p>
 * 0 <= index < length<p>
 * 0 <= snap_id < 我们调用 snap() 的总次数<p>
 * 0 <= val <= 10^9<p>
 */
public class LeetCode1146 {

    @Test
    public void test01() {
        // 初始化一个长度为 3 的快照数组
        SnapshotArray snapshotArr = new SnapshotArray(3);
        // 令 array[0] = 5
        snapshotArr.set(0, 5);
        // 获取快照，返回 snap_id = 0
        System.out.println(snapshotArr.snap());
        snapshotArr.set(0, 6);
        // 获取 snap_id = 0 的快照中 array[0] 的值，返回 5
        System.out.println(snapshotArr.get(0, 0));
    }
}

class SnapshotArray {

    int snapId;
    int length;
    Map<Integer, Integer> map;
    Map<Integer, Map<Integer, Integer>> snap;

    /**
     * 初始化一个与指定长度相等的 类数组 的数据结构。初始时，每个元素都等于 0。
     *
     * @param length 指定数据的长度
     */
    public SnapshotArray(int length) {
        this.length = length;
        snapId = 0;
        map = new HashMap<>();
        snap = new HashMap<>();
    }

    /**
     * 会将指定索引 index 处的元素设置为 val。
     *
     * @param index 索引
     * @param val   值
     */
    public void set(int index, int val) {
        map.put(index, val);
    }

    /**
     * 获取该数组的快照，并返回快照的编号 snap_id（快照号是调用 snap() 的总次数减去 1）。
     *
     * @return 获取快照
     */
    public int snap() {
        snap.put(snapId, new HashMap<>(map));
        snapId++;
        return snapId - 1;
    }

    /**
     * 根据指定的 snap_id 选择快照，并返回该快照指定索引 index 的值。
     *
     * @param index   索引
     * @param snap_id snap_id
     * @return 索引的值
     */
    public int get(int index, int snap_id) {
        Map<Integer, Integer> integerMap = snap.get(snap_id);
        return integerMap.getOrDefault(index, 0);
    }
}

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * SnapshotArray obj = new SnapshotArray(length);
 * obj.set(index,val);
 * int param_2 = obj.snap();
 * int param_3 = obj.get(index,snap_id);
 */
